#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<unordered_map>
#include<set>
using namespace std;

class Solution {
public:
    int balancedStringSplit(string s) {
        int num = 0;
        int ret = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == 'L')
            {
                num++;
            }
            else
            {
                num--;
            }
            if (num == 0)
            {
                ret++;
            }
        }
        return ret;
    }

    // void Backtracking(string& str,set<string>& ret,vector<int>& flag,string s,int pos)
    // {
    //    //pos代表遍历到str的pos位置了
    //     if(s.size()==str.size())
    //     {
    //         ret.insert(s);
    //         return;
    //     }

    //     flag[pos]=1;
    //     for(int i=0;i<str.size();i++)
    //     {
    //         if(flag[i]==0)
    //         {
    //             s.push_back(str[i]);
    //             Backtracking(str, ret,flag, s, i);
    //             s.pop_back();
    //         }
    //     }
    //     flag[pos]=0;
    // }

    void Backtracking(string& str, set<string>& ret, vector<int>& flag, string& s, int pos)
    {
        //pos代表填s的pos位置
        if (pos == str.size())
        {
            ret.insert(s);
        }

        for (int i = 0; i < str.size(); i++)
        {
            if (flag[i] == 0)
            {
                if (i > 0 && str[i - 1] == str[i] && flag[i - 1] == 0)
                {//剪枝，若i位置与i-1位置相同，且i-1位置没有使用(已经回溯了)，直接跳过该次循环
                    continue;
                }
                flag[i] = 1;
                s.push_back(str[i]);
                Backtracking(str, ret, flag, s, pos + 1);
                s.pop_back();
                flag[i] = 0;
            }
        }
    }

    vector<string> Permutation(string str)
    {
        set<string> ret;
        vector<int> flag(str.size(), 0);
        string s;
        // for(int i=0;i<str.size();i++)
        // {
        //     s.push_back(str[i]);
        //     Backtracking(str,ret,flag,s,i);
        //     s.pop_back();
        // }
        sort(str.begin(), str.end());//先排序，提高剪枝效率
        Backtracking(str, ret, flag, s, 0);
        vector<string> v(ret.begin(), ret.end());
        return v;
        // write code here
    }

    
    //int solve(vector<vector<int> >& matrix)
    //{
    //    int m = matrix.size();
    //    int n = matrix[0].size();
    //    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    //    //dp[i][j]表示到达(i,j)位置时的最大递增路径的长度
    //    //dp1[i][j]=matrix[i-1][j]<matrix[i][j]?(dp[i-1][j]+1):1
    //    //dp2[i][j]=matrix[i][j-1]<matrix[i][j]?(dp[i][j-1]+1):1
    //    //dp[i][j]=max(dp1,dp2)

    //    int i = 0, j = 0;
    //    int Max = 0;
    //    dp[1][1] = 1;
    //    for (i = 2; i < m; i++)
    //    {
    //        dp[i][1] = matrix[i - 1 - 1][0] < matrix[i - 1][0] ? dp[i - 1][1] + 1 : 1;
    //    }
    //    
    //    for (j = 2; j < n; j++)
    //    {
    //        dp[1][j] = matrix[0][j - 1 - 1] < matrix[0][j - 1] ? dp[1][j - 1] + 1 : 1;
    //    }

    //    for (i = 2; i <= m; i++)
    //    {
    //        for (j = 2; j <= n; j++)
    //        {
    //            int dp1 = matrix[i - 1 - 1][j - 1] < matrix[i - 1][j - 1] ? (dp[i - 1][j] + 1) : 1;
    //            int dp2 = matrix[i - 1][j - 1 - 1] < matrix[i - 1][j - 1] ? (dp[i][j - 1] + 1) : 1;
    //            dp[i][j] = max(dp1, dp2);
    //            if (dp[i][j] > Max)
    //            {
    //                Max = dp[i][j];
    //            }
    //        }
    //    }
    //    return Max;
    //    // write code here
    //}

    //能往上下左右四个方向移动
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };

    int dfs(vector<vector<int>>& flag, vector<vector<int>>& matrix, int i, int j, int m, int n)
    {
        if (flag[i][j] != -1)//(i,j)位置已经遍历过了，即已经知道了从(i,j)位置出发能走的最大长度
        {
            return flag[i][j];
        }
        int len = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
            {
                len = max(len, 1 + dfs(flag, matrix, x, y, m, n));
            }
        }
        flag[i][j] = len;
        return len;

    }
    int solve(vector<vector<int> >& matrix)
    {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> flag(m, vector<int>(n, -1));
        //flag[i][j]表示从(i,j)位置出发，可以走的最大路径长度
        int ret = 1;
        for (int i = 0; i < m; i++)//遍历每一个起点
        {
            for (int j = 0; j < n; j++)
            {
                ret = max(ret, dfs(flag, matrix, i, j, m, n));
            }
        }
        return ret;

        // write code here
    }
};

//int main()
//{
//    string str;
//    cin >> str;
//    int n = str.size();
//    unordered_map<char, int> mp;
//    int l = 0, r = 0;
//    int maxlen = 0;
//    while (r < n)
//    {
//        mp[str[r]]++;
//        while (mp.size() > 2)//[l,r]区间内超过三种字符
//        {
//            mp[str[l]]--;
//            if (mp[str[l]] == 0)
//            {
//                mp.erase(str[l]);
//            }
//            l++;
//        }
//        int len = r - l + 1;
//        maxlen = max(len, maxlen);
//        r++;
//    }
//    cout << maxlen << endl;
//    return 0;
//}

int main()
{
    Solution S;
    string s = "aab";
    S.Permutation(s);

    vector<vector<int>> v{ {1,2,3},{4,5,6},{7,8,9} };
    cout<<S.solve(v);
    return 0;
}

//int main()
//{
//    string str;
//    cin >> str;
//    const char sep = '-';//分隔符
//    int sum = 0;
//    int count = 1;
//    for (auto& e : str)//求和
//    {
//        if (e != sep)
//        {
//            sum += (e - '0') * count;
//            count++;
//            if (count >= 10)
//            {
//                break;
//            }
//        }
//    }
//    sum %= 11;
//    if ((str[str.size() - 1] == 'X' && sum == 10) || (str[str.size() - 1] - '0') == sum)
//    {
//        cout << "Right" << endl;
//    }
//    else
//    {
//        if (sum == 10)
//        {
//            str[str.size() - 1] = 'X';
//        }
//        else
//        {
//            str[str.size() - 1] = sum + '0';
//        }
//        cout << str << endl;
//    }
//    return 0;
//}